The puzzle:
You place 100 coins heads up in a row and number them by position, with the coin all the way on the left No. 1 and the one on the rightmost edge No. 100. Next, for every number N, from 1 to 100, you flip over every coin whose position is a multiple of N. For example, first you'll flip over all the coins, because every number is a multiple of 1. Then you'll flip over all the even-numbered coins, because they're multiples of 2. Then you'll flip coins No. 3, 6, 9, 12, and so on.
What do the coins look like when you're done? Specifically, which coins are heads down?
Answer:
If you begin with all coins heads facing up all of the coins will end up flipped heads down. They should end up being flipped on the opposite side that they were placed on to begin with before flipping.
Discussion:
I chose this puzzle out of 7 because it looked interesting from both a mathematical and programming angle and also easily implementable. If I had not solved this puzzle using an algorithm I would have spent most of my time tediously flipping coins and hopefully keeping track accurately in order to end up with the right results. This made it a perfect problem to apply from a computer science perspective, afterall all software which are algorithms serve the purpose of taking large tasks and solving them quickly doing most of the work for the user.
Not only did this puzzle have an interesting programming angle, while solving the problem which took two attempts on my part I found myself wondering what the mathematical basis for this problem is. My algorithm asks for each coin and step (which we can let be N), "Is the coin's number divisible by N such that it becomes equal to 0?" If yes, we flip the coin. This is a different question than "Is the coin's number a multiple of N?", which implicates a couple of things. One, my algorithm wouldn't be able to work with negative numbers, more on that in a second. Two, also that it wouldn't be able to work with decimals or non-whole numbers, because it counts each step using whole numbers. Finally and most fascinating, this puzzle seems to demonstrate the properties of multiplicative inverse. This was revealed to me in my first attempt when I was printing out each flip (step) to the terminal as I was coding the algorithm. I hope to demonstrate this with a picture at the end of my notes.
First import coins.py, using sys to traverse up a directory though...
In [1]:
import sys
sys.path.append('../')
from coins import *
We start with coins facing heads up:
In [2]:
coins = gen_coins(heads='+')
print(coins)
Then we use the algorithm to do the flipping for us:
In [3]:
flipped_coins = flip_coins(coins, tails='-')
print(flipped_coins)
""" coins.py | Tue, Feb 07, 2017 | Roman S. Collins The problem: You place 100 coins heads up in a row and number them by position, with the coin all the way on the left No. 1 and the one on the rightmost edge No. 100. Next, for every number N, from 1 to 100, you flip over every coin whose position is a multiple of N. For example, first you'll flip over every coin whose position is a multiple of N. For example. First you'll flip over all the coins, because every number is a multiple of 1. Then you'll flip over all the even-numbered coins, because theyre multiples of 2. Then you'll flip coins No. 3, 6, 9, 12 and so on. """ def gen_coins(heads='.', n=100): for i in range(1, n + 1): coins = heads * n return coins def flip_coins(coins, tails='·'): flipped_coins = [] for c in range(len(coins)): flipped_coins.append(coins[c]) for i in range(len(flipped_coins)): for n in range(len(flipped_coins)): if i == 0: flipped_coins[i] = tails try: if n % i == 0: flipped_coins[i] = tails #print((n % i), end='') except ZeroDivisionError: pass return ''.join(flipped_coins) def main(): coins = gen_coins(heads='-') print('') print(coins) flipped_coins = flip_coins(coins, tails='+') print('') print(flipped_coins) if __name__ == '__main__': main()
(The result is beautiful.)
In [7]:
def gen_coins(heads='.', n=100):
for i in range(1, n + 1):
coins = heads * n
return coins
def flip_coins(coins, tails='·'):
flipped_coins = []
for c in range(len(coins)):
flipped_coins.append(coins[c])
for i in range(len(flipped_coins)):
for n in range(len(flipped_coins)):
if i == 0:
flipped_coins[i] = tails
try:
if n % i == 0:
flipped_coins[i] = tails
#print((n % i), end='')
except ZeroDivisionError:
pass
print(''.join(flipped_coins))
return ''.join(flipped_coins)
def main():
coins = gen_coins(heads='-', n=100)
#print('')
#print(coins)
flipped_coins = flip_coins(coins, tails='+')
#print('')
#print(flipped_coins)
if __name__ == '__main__':
main()
In [ ]: